#!/usr/bin/python
import math

def summable(A, x):
	'''Returns true if there exists a pair of elements in A that sum to
	x, false otherwise.'''
	if len(A) == 1 or len(A) == 0:
		return False
	elif len(A) == 2:
		return A[0] + A[1] == x
	elif len(A) == 3:
		return A[0] + A[1] == x or A[1] + A[2] == x or A[0] + A[2] == x
	else:
		swap_i = 0
		midpoint = int(math.floor((len(A) + 1) / 2))
		#while there are still pairs left to be checked
		while swap_parter(A, swap_i) < len(A):
			print A
			if swap_i != 0: swap(A, swap_i, swap_parter(A, swap_i))
			if summable(A[0:(midpoint+1)], x) or summable(A[(midpoint+1):len(A)], x):
				return True
			swap_i += 1
	return False

def swap_parter(A, i):
	'''Returns the index of the element in A that should be swapped with
	the element at i in A.'''
	return i + int(math.ceil(len(A)/2))

def swap(A, swap_i, swap_with):
	'''Swaps the element in A at swap_i with the element at swap_with.'''
	A[swap_i], A[swap_with] = A[swap_with], A[swap_i]

def inefficient_summable(A, x):
	for i in range(0, len(A)):
		for j in range(0, len(A)):
			if i != j:
				if A[i] + A[j] == x: return True
	return False
					
if __name__ == '__main__':
	A = []
	i = 0
	while i < 100:
		A.append(i)
		i += 1
	print inefficient_summable(A, 100)
